平面图

一.定义
若能将无向图 G=(V,E)G=(V,E) 画在平面上使得任意两条无重合顶点的边不相交,则称 GG 是平面图。

在平面图中,由边构成的最小区域称为面,包围该面的边数记为该面的度,特殊的,平面图外的区域也为一个面。

阅读全文 »

二分图

一.二分图的基本知识

1.二分图的概念

       ~~~~~~~二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集,则称图G为一个二分图。我们一般把其中一部分称为x部,另一部分称为y部。

阅读全文 »

强连通分量

一.强连通分量的定义

有向图G中,如果两个顶点vi,vj间(vi!=vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径(即两点互相可达),则称两个顶点强连通。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量。

一个有向图是强连通的,当且仅当G中有一个回路,它至少包含每个节点一次。

阅读全文 »